package com.mdnote.practice.disjointed_set;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/24
 * @description 朋友圈
 */
public class LeetCode547 {

    public static void main(String[] args) {
        LeetCode547 leetCode547 = new LeetCode547();

        int[][] M = {
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1},
                {1,1,1,1}
        };
        int circleNum = leetCode547.findCircleNum(M);
        System.out.println(circleNum);
    }

    /**
     * 是不是看看这个朋友图中有多少个环呀，最后人数 - 环数就是答案
     * @param M
     * @return
     */
    public int findCircleNum(int[][] M) {

        int[] parent = new int[M.length];
        // 自己指向自己
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        int count = 0;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {
                if (M[i][j] == 1) {
                    int union = union(i, j, parent);
                    if (union == 0) {
                        // 返现一个圈子
                        count++;
                    }
                }
            }

        }
        System.out.println(count);
        return M.length - count;
    }


    public int find_parent(int x, int[] parent) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }

    private int union(int x, int y, int[] parent) {
        int x_root = find_parent(x, parent);
        int y_root = find_parent(y, parent);

        if (x_root == y_root) {
            return -1;
        } else {
            while (x != parent[x]) {
                int t = parent[x];
                parent[x] = y_root;
                x = t;
            }
            parent[x_root] = y_root;
        }
        return 0;
    }
}
